class Trie {

        class TrieNode {
            private TrieNode[] links;

            private final int R = 26;

            private boolean isEnd;

            public TrieNode() {
                links = new TrieNode[R];
            }

            public boolean containKey(char ch) {
                return links[ch - 'a'] != null;
            }

            public TrieNode get(char ch) {
                return links[ch - 'a'];
            }

            public void put(char ch, TrieNode node) {
                links[ch - 'a'] = node;
            }

            public void setEnd() {
                isEnd = true;
            }

            public boolean isEnd() {
                return isEnd;
            }
        }

        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        // 插入一个单词
        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); ++i) {
                // 将插入的word拆分为一个一个的字符
                char currentChar = word.charAt(i);
                // 如果当前TrieNode不包含当前字符
                if (!node.containKey(currentChar)) {
                    node.put(currentChar, new TrieNode());
                }
                node = node.get(currentChar);
            }
            node.setEnd();
        }

        // 在 Trie 树中查找键
        // 在Trie树中查找是否存在某个单词
        public boolean search(String word) {
            TrieNode node = searchPrefix(word);
            return node != null && node.isEnd();
        }

        // 查找 Trie 树中查找是否存在以某个单词为前缀的单词(包括该单词本身)，存在则返回该node
        private TrieNode searchPrefix(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); ++i) {
                char curLetter = word.charAt(i);
                if (node.containKey(curLetter)) {
                    // 移动到下一个节点
                    node = node.get(curLetter);
                } else {
                    return null;
                }
            }
            return node;
        }

        // 查找 Trie 树中查找是否存在以某个单词为前缀的单词(包括该单词本身)
        // trie.insert("apple");
        //trie.search("app");  返回 false
        //trie.startsWith("app"); 返回 true
        public boolean startsWith(String prefix) {
            TrieNode node = searchPrefix(prefix);
            return node != null;
        }
    }